package mo.tags.stack;

import java.util.ArrayDeque;
import java.util.Deque;

public class L402 {

    //"1432219"
    //3



    public String removeKdigits(String num, int k) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < num.length(); i++) {
            int cur = num.charAt(i)-'0';
            while (!stack.isEmpty() && k > 0 && stack.peekLast() > cur) {
                stack.pollLast();
                k--;
            }
            stack.offerLast(cur);
        }

        for (int i = 0; i < k; i++) {
            stack.pollLast();
        }

        StringBuilder builder = new StringBuilder();
        boolean leadingZero = true;
        while (!stack.isEmpty()) {
            Integer cur = stack.pollFirst();
            if (!leadingZero || cur != 0) {
                builder.append(cur);
                leadingZero = false;
            }
        }
        return builder.length() == 0 ? "0" : builder.toString();
    }

    public static void main(String[] args) {
        L402 test = new L402();
        System.out.println(test.removeKdigits("1432219", 3));
    }

}
